Given an undirected graph with costs associated with each edge as well aseach pair of edges, the quadratic minimum spanning tree problem (QMSTP)consists of determining a spanning tree of minimum total cost. This problem canbe used to model many real-life network design applications, in which bothrouting and interference costs should be considered. For this problem, wepropose a three-phase search approach named TPS, which integrates 1) adescent-based neighborhood search phase using two different move operators toreach a local optimum from a given starting solution, 2) a local optimaexploring phase to discover nearby local optima within a given regional searcharea, and 3) a perturbation-based diversification phase to jump out of thecurrent regional search area. Additionally, we introduce dedicated techniquesto reduce the neighborhood to explore and streamline the neighborhoodevaluations. Computational experiments based on hundreds of representativebenchmarks show that TPS produces highly competitive results with respect tothe best performing approaches in the literature by improving the best knownresults for 31 instances and matching the best known results for the remaininginstances only except two cases. Critical elements of the proposed algorithmsare analyzed.
展开▼
